//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 
//
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
//
// 注意：给定 n 是一个正整数。 
//
// 示例 1： 
//
// 输入： 2
//输出： 2
//解释： 有两种方法可以爬到楼顶。
//1.  1 阶 + 1 阶
//2.  2 阶 
//
// 示例 2： 
//
// 输入： 3
//输出： 3
//解释： 有三种方法可以爬到楼顶。
//1.  1 阶 + 1 阶 + 1 阶
//2.  1 阶 + 2 阶
//3.  2 阶 + 1 阶
// 
// Related Topics 动态规划 
// 👍 1391 👎 0

package homework.algorithm.Week_01.jqb;

//Java：爬楼梯
public class P70ClimbingStairs {
    public static void main(String[] args) {
        Solution solution = new P70ClimbingStairs().new Solution();
        // TO TEST
        int n = 4;
        System.out.println(solution.climbStairs(n));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //解决算法问题思路: 找 最近重复子问题，然后通过if else ，for while 这类loop 或者 递归（recursion）来解决
        //本题分析：
        //1、一级台阶，一步就可跨过，所以是1种方法
        //2、二级台阶，一步跨两级，或者 一步上一级， 所以是2种方法
        //3、三级台阶，一步上一级；先上一级，再上两级；或者先上两级，再上一级，所以是3种方法
        //4、四级台阶，共5中方法
        //  一步上一级；
        //  先上一级，再上两级，再上一级；
        //  先上一级，再上一级，再上两级；
        //  先上两级，再上一级，再上一级；
        //  先上两级，再上两级；
        //结论： 以此类推，上到第n级台阶，相当于将上到第（n-1）级台阶的方法 加上 第（n-2)级台阶的方法相加即可，公式为：f(n) = f(n-1) + f(n-2). 斐波那契数列 fibonacci

        public int climbStairs(int n) {
            if (n <= 2) {
                return n;
            }
            int f1 = 1, f2 = 2, f3 = 3;
            for (int i = 3; i < n; i++) {
                f1 = f2;
                f2 = f3;
                f3 = f1 + f2;
            }
            return f3;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
